//
// Created by LiuYou on 2021/5/25.
//

#include <cstdlib>
#include <set>
#include <string>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <iterator>

#define DEBUG

/**
 * @brief 集合覆盖问题
 *
 * 这个02版本将功能实现了。但是我也做了03版本帮助我理解。
 */
int main() {
    // 8个
    // 传入一个数组, 它被转换为集合。
    // 要覆盖8个州
    std::set<std::string> statesNeeded({"mt", "wa", "or", "id", "nv", "ut", "ca", "az"});
//    std::set<std::string> statesNeeded({std::string("mt"), std::string("wa"), std::string("or"), std::string("id"),
//                                        std::string("nv"), std::string("ut"), std::string("ca"), std::string("az")});


#ifdef DEBUG
    std::cout << "statesNeeded: " << std::endl;
    for (const auto& item : statesNeeded) {
        std::cout << item << std::endl;
    }
    std::cout << std::endl;
#endif

    // 广播台
    // 可供选择的广播台清单, 使用散列表来存储。
    std::__umap_hashtable<std::string, std::set<std::string>> stations{};
    stations["kone-1"] = std::set<std::string>({"id", "nv", "ut"});
    stations["ktwo-2"] = std::set<std::string>({"wa", "id", "mt"});
    stations["kthree-3"] = std::set<std::string>({"or", "nv", "ca"});
    stations["kfour-4"] = std::set<std::string>({"nv", "ut"});
    stations["kfive-5"] = std::set<std::string>({"ca", "az"});

    // 最终选择的广播台
    // 使用一个集合来存储最终选择的广播台。
    using SetString = std::set<std::string>;
    SetString finalStations;

    // 算法:
    // 选择覆盖了最多的未覆盖州的广播台。将这个广播台存储在 bestStation内。
    // TODO 注意: 问题: bestStation是什么? 是集合还是散列表还是pair?
    //  我觉得是散列表
    //  不对, 应该就是一个字符串
    //  通过不断调试确定了 bestStation确实是stations散列表的键, 即字符串！！！！
//    std::__umap_hashtable<std::string, std::set<std::string>> bestStation{};
//    std::pair<std::string, SetString> bestStation{};
//    std::string bestStation{};
    // statesCovered是一个集合, 包含该广播台覆盖的所有未覆盖的州。
//    SetString statesCovered{};

#ifdef DEBUG
    // TODO 注意: 通过调试阶段对 stations的观察发现
    //  C++ 的散列表 std::__umap_hashtable对键值对中的值会进行排序(如果值有顺序的话)！！！！
    //  而且另外一个重点: std::__umap_hashtable不会对键值进行排序。就是之后顺序遍历散列表的时候, 散列表的输出顺序与你插入键值对时的顺序是不同的！！！！这一点非常重要！！！！
    std::cout << "stations: " << std::endl;
    for (const auto& item : stations) {
        std::cout << item.first << " ";
        for (const auto& elem : item.second) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
#endif

//    for (const auto& item : statesNeeded) {
    while (!statesNeeded.empty()) {
        // TODO 注意: 这里知道了为什么将while循环中每次循环使用到的对象定义在循环之外！！！！
        //  因为每次对象的创建和销毁都需要时间消耗！！！！
        //  这里非常重要！！！！！！！！！！！！！！！！！！！！！！！
        std::string bestStation{};
        SetString statesCovered{};
//        bestStation = "";
//        statesCovered = std::set<std::string>();

        std::cout << "内层for开始" << std::endl;

        // for循环迭代每个广播台, 并确定它时候是最佳的广播台
        for (const auto& item : stations) {
            std::set<std::string> statesForStation = item.second;
            // 计算每一个item, 即广播台覆盖的州与想要覆盖的8个州的交集。
            std::set<std::string> covered{};
            // TODO 注意: 报错
            //   error: passing ‘const std::__cxx11::basic_string<char>’ as ‘this’ argument discards qualifiers
            std::set_intersection(statesNeeded.begin(), statesNeeded.end(),
                                  statesForStation.begin(), statesForStation.end(),
                                  std::inserter(covered, std::begin(covered)));
//            std::set_intersection(statesNeeded.begin(), statesNeeded.end(),
//                                  statesForStation.begin(), statesForStation.end(),
//                                  covered);


            if (covered.size() > statesCovered.size()) {
                bestStation = item.first;
                statesCovered = covered;
            }
        }
        std::cout << "内层for结束" << std::endl;

//        statesNeeded -= statesCovered;
        std::set<std::string> tmp{};
/*        std::set_difference(statesNeeded.begin(), statesNeeded.end(),
                            statesCovered.begin(), statesCovered.end(),
                            tmp.begin());*/
        std::set_difference(statesNeeded.begin(), statesNeeded.end(),
                            statesCovered.begin(), statesCovered.end(),
                            std::inserter(tmp, std::begin(tmp)));

//        statesNeeded = tmp;
        // TODO 注意: 这里没有进行上一条注释语句的赋值, 而是先将 statesNeeded清空, 然后将 tmp赋值到 statesNeeded。
        statesNeeded.clear();
        statesNeeded = tmp;

        for (const auto& needed : statesNeeded) {
            std::cout << "needed: " << needed << std::endl;
        }

        finalStations.insert(bestStation);
        std::cout << "======================" << std::endl;
        for (const auto& item : finalStations) {
            std::cout << item << std::endl;
        }
        std::cout << "======================" << std::endl;
    }

    for (const auto& item : finalStations) {
        std::cout << item << std::endl;
    }

















    // P123~P124
//    // for循环迭代每个广播台, 并确定它时候是最佳的广播台
//    for (const auto& item : stations) {
//        std::set<std::string> statesForStation = item.second;
//        // 计算每一个item, 即广播台覆盖的州与想要覆盖的8个州的交集。
//        std::set<std::string> covered{};
//        std::set_intersection(statesNeeded.begin(), statesNeeded.end(),
//                              statesForStation.begin(), statesForStation.end(),
//                              covered.begin());
//        if (covered.size() > statesCovered.size()) {
////            bestStation = stations;
//            bestStation = item;
//            statesCovered = covered;
//        }
//    }





















    // 从SetCoverProblem01.cpp继承来的内容。
//    for (auto& item : stations) {
//        for (auto& setItem : item.second) {
////            (std::string) (setItem);
//            // TODO 注意:
//            //  这里不知道为什么会报错！
//            //   error: no match for ‘operator<’ (operand types are ‘const char’ and ‘const std::__cxx11::basic_string<char>’)
//            //   error: no match for ‘operator<’ (operand types are ‘const std::__cxx11::basic_string<char>’ and ‘const char’)
//            //       { return *__it1 < *__it2; }
//            //                ~~~~~~~^~~~~~~~
//            std::set_intersection(statesNeeded.cbegin(), statesNeeded.cend(), setItem.cbegin(), setItem.cend(),
//                                  std::ostream_iterator<std::string>(std::cout, " ")/*,*/
//                    /*std::equal_to<std::string>(statesNeeded, setItem)*/);
//
//        }
//    }


    std::exit(0);
}